package com.zjsru.plan2023.oneday;

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @Author: cookLee
 * @Date: 2023-11-29
 * 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 */
public class FindKthLargest {

    /**
     * 主
     * \
     * 输入: [3,2,1,5,6,4], k = 2
     * 输出: 5
     * \
     * 输入: [3,2,3,1,2,4,5,5,6], k = 4
     * 输出: 4
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindKthLargest findKthLargest = new FindKthLargest();
        int[] nums = new int[]{3,2,1,5,6,4};
        int k = 2;
        System.out.println(findKthLargest.findKthLargest(nums, k));
    }

    /**
     * 找到最大kth
     * 排序
     * @param nums nums
     * @param k    k
     * @return int
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    /**
     * 找到最大kth:优先队列，类似于第一种排序的变种
     *
     * @param nums nums
     * @param k    k
     * @return int
     */
    public int findKthLargest2(int[] nums, int k) {
        if (nums == null || nums.length < k || k == 0) {
            return Integer.MIN_VALUE;
        }
        //倒序
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : nums) {
            priorityQueue.add(num);
        }
        //缩减k，将不符合的都弹出队列
        while (k > 1) {
            priorityQueue.poll();
            k--;
        }
        //此时队列的头元素即是答案
        return priorityQueue.isEmpty() ? Integer.MIN_VALUE : priorityQueue.peek();
    }

}
